//反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 
//
// 说明: 
//1 ≤ m ≤ n ≤ 链表长度。 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL, m = 2, n = 4
//输出: 1->4->3->2->5->NULL 
// Related Topics 链表 
// 👍 644 👎 0

package leetcode.editor.cn;
//Java：反转链表 II
public class ReverseLinkedListIi{
    public static void main(String[] args) {
        Solution solution = new ReverseLinkedListIi().new Solution();
        
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
   }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    //后继结点
    ListNode successorNode = null ;
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if ( m == 1 ){
            return reverseN(head,n);
        }
        head.next = reverseBetween(head.next, m-1 ,n-1);
        return head;
    }

    //翻转前n个节点
    public ListNode reverseN(ListNode head, int n) {
        if ( n == 1 ){
            //记录第 n+1 个节点，也就是后继结点
            successorNode = head.next;
            //返回第 n 个节点，也就是新的头节点
            return head;
        }
        //以第一个head.next开始，往后翻转n-1个节点
        //这个变量记录的是第n个节点的值，递归函数
        ListNode newHead = reverseN( head.next, n-1 );

        //最后一次翻转head和head.next
        head.next.next = head;
        //把head的下一个节点指向后继结点
        head.next = successorNode;
        //递归返回最后一次的函数
        //此时返回的newHead节点是第n个节点
        return newHead;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
